package 算法.leetcode.labuladong.数组和链表;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author lchenglong
 * @date 2022/6/18
 */
public class 队列中可以看到的人数 {
    static class Solution {

        public static void main(String[] args) {
            Solution solution = new Solution();
            int[] heights = new int[]{10,6,8,5,11,9};
            int[] ints = solution.canSeePersonsCount(heights);
            System.out.println(Arrays.toString(ints));
        }
        public int[] canSeePersonsCount(int[] heights) {
            int[] ans = new int[heights.length];
            // 单调递增栈
            Stack<Integer> s = new Stack<>();
            for (int i=heights.length-1;i>=0;i--) {
                // 记录右侧比自己矮的人
                int count = 0;
                // s.peek()<heights[i] 后面比自己矮的人
                while (!s.isEmpty()&&s.peek()<heights[i]){
                    s.pop();
                    count++;
                }
                // 不仅可以看到比自己矮的人，如果后面存在更高的的人，也可以看到这个高人
                ans[i] = s.isEmpty()?count:count+1;
                s.push(heights[i]);
            }
            return ans;
        }
    }
}
